package 左哥算法.ch10暴力递归;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 在动态规划那一栏中，已经使用递归的方式解决过一次八皇后问题，但那次的代码优化空间很大，这次采用另一种方式去写八皇后问题
 *  在上一次的过程中，是使用一个二维数组，对每一层进行递归，尝试放入该层的节点，对该节点的列，左斜线，有斜线进行验证。将符合要求的要求的放入数组中
 *  第一次优化：
 *  在这个过程中，有哪些地方是可以优化的呢？
 *      1.真的需要一个二维数组吗？
 *          每一行都只有一个信息，就是皇后在哪一列，那这就可以用一维数组表示
 *      2.之前验证是否符合要求时，是遍历了数组3次（列一次，左斜线一次，右斜线一次），真的需要遍历3次吗？
 *          列：判断是否与之前的元素在同一列，即arr[curr]!=arr[n]
 *          斜线：判断当前节点到之前节点的行距离与列距离是否相同，即 arr[curr]-arr[n]!=curr-n。（当然，左右都要为正数）
 *          如此看来，好像列和斜线需要的信息（curr和n）都可以在同一个遍历中获得，是不是可以将遍历化为一个？答案是可以的
 * 第二次优化：
 *   在第一次优化中，已经将代码的可以通用的地方都已经公用了，第二次还能优化些什么呢？
 *      1.判断是否能填皇后，是通过判断之前的皇后对当前行做出的限制，
 *          如：列限制，其他皇后不能与我同一列；左斜线限制，其他皇后不能在我的左斜线上；右斜线限制：其他皇后不能在我右斜线上
 *          也就是说，只需要知道之前皇后对当前行的限制有哪些，就可以知道当前行哪些位置可以放皇后
 *      2.一行中存放皇后的信息需要什么？皇后的状态只有两种，存在或不存在（0或1）
 *          既然如此，我是不是可以用一个n长度的二进制数来表示这一行哪些位置可以放皇后，哪些位置不能放皇后
 * 思路：
 *      1.准备三个限制，列限制，左斜线限制，右斜线限制.（1表示不能放，0表示可以放）
 *      2.通过 之前皇后的 列限制|左限制|右限制  可以的出当前行哪些位置不能摆放皇后（取反一下就是哪些位置可以放皇后）
 *          如果列限制已经摆满了，则表示这是一个符合要求的结果
 *      3.当前行放入皇后后，将当前皇后加入限制，即将皇后位置对三个限制进行或运算。
 *      4.并对下一行进行限制，即列不动，左限制左移一位，右限制右移一位。递归判断之后的皇后是否符合要求。
 *          如果之后的皇后不符合要求，则挑选当前行的另一个皇后递归，如果当前行所有皇后都不符合，则返回0
 *          如果之后的皇后符合要求，则将他们的结果保存，换当前行的其他皇后进行递归，直到当前行所有的皇后都递归完成
 */
public class Ch010八皇后问题plus {


    /**
     * 第一次优化：
     */
    @Test
    public void test0(){

    }

    @Test
    public void test01(){
        ArrayList<String> list=new ArrayList<>();
        list.add("");
        int n=8;
        int limit=(1<<n)-1; //让右侧变为n个1
        System.out.println(solveNQueens(limit, 0, 0, 0));
    }
    /**
     * ch01：八皇后问题不存放结果
     */
    public int solveNQueens(int limit,int colLimit,int leftLimit,int rightLimit){
        if (limit==colLimit){
            return 1;
        }
        int pos=limit&(~(colLimit|leftLimit|rightLimit));  //求出哪些位置可以放皇后,limit是防止二进制位跑到左侧
        int curr=pos&(~pos+1);   //找到最右侧的1，(可以放皇后的位置)
        int res=0;  //用于存放结果
        while (pos!=0){
            //之前的限制加上当前皇后的限制
            res+=solveNQueens(
                    limit,
                    colLimit|curr,
                    (leftLimit|curr)<<1,
                    (rightLimit|curr)>>1
            );
            pos-=curr;
            curr=pos&(~pos+1);
        }
        return res;
    }


    @Test
    public void test02(){
        List<List<String>> lists = solveNQueens(8);
        for (int i = 0; i < lists.size(); i++) {
            System.out.println("---"+(i+1)+"---");
            lists.get(i).forEach(System.out::println);
        }
    }

    List<List<String>> lists=new ArrayList<>();
    char[] chars;
    /**
     * ch02：八皇后问题存放结果
     * @param n:皇后数量
     * @return  原本是返回具体的解法
     */
    public List<List<String>> solveNQueens(int n) {
        chars=new char[n];
        Arrays.fill(chars,'.');
        int limit=(1<<n)-1; //让右侧变为n个1
        solveNQueens(limit, 0, 0, 0,new int[n],0);
        return lists;
    }

    /**
     * @param limit：用于限制二进制不越位到左侧
     * @param colLimit：列限制
     * @param leftLimit：左斜线限制
     * @param rightLimit：右斜线限制
     *  如果不需要存放结果，下面两个可以省略
     * @param arr：用于存放皇后位置的数组
     * @param n：第几层
     */
    public void solveNQueens(int limit, int colLimit, int leftLimit, int rightLimit,int[] arr,int n){
        if (limit==colLimit){
            lists.add(create(arr));
            return;
        }
        int pos=limit&(~(colLimit|leftLimit|rightLimit));  //求出哪些位置可以放皇后,limit是防止二进制位跑到左侧
        int curr=0;
        while (pos!=0){
            curr=pos&(~pos+1);  //找到最右侧的1，(可以放皇后的位置)
            arr[n]=arr.length-(int)(Math.log(curr)/Math.log(2)+1); //放入皇后
            //之前的限制加上当前皇后的限制
            solveNQueens(
                    limit,
                    colLimit|curr,
                    (leftLimit|curr)<<1,
                    (rightLimit|curr)>>1,
                    arr,n+1
            );
            pos-=curr;
        }
    }

    public List<String> create(int[] arr){
        List<String> list=new ArrayList<>();
        for (int i = 0; i < arr.length; i++) {
            chars[arr[i]]='Q';
            list.add(new String(chars));
            chars[arr[i]]='.';
        }
        return list;
    }
}
